package binarytree

func searchBST(root *TreeNode, val int) *TreeNode {
	// 二叉搜索树就是 左子树 < 根节点 < 右子树
	// 所以搜索目标值从根节点开始比较，比根节点小的话，那么我们就去左子树找，找的方式相同(子问题递归)，直到nil
	if root == nil {
		return nil
	}

	if val == root.Val {
		return root
	} else if val < root.Val {
		return searchBST(root.Left, val)
	} else {
		return searchBST(root.Right, val)
	}
}
